package graph;

import org.junit.Test;

import java.net.HttpURLConnection;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author DuJiabao
 * @create 2021-01-02 22:01
 */
public class Graph {
    private int v;
    private LinkedList<Integer>[] adj;
    private boolean found;

    public Graph() {
    }

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v]; // 链表的数组
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList();  //每一个位置保存一个链表
        }
    }

    /**
     * 无向图，两个顶点
     *
     * @param s
     * @param t
     */
    public void addEdge(int s, int t) {
        adj[s].add(t);
        adj[t].add(s);
    }

    public void bfs(int start, int des) {
        if (start == des) return;
        boolean visited[] = new boolean[v]; //记录是否被visit了
        visited[start] = true;

        int prev[] = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }

        Queue<Integer> queue = new LinkedList();
        queue.add(start);

        while (queue.size() > 0) {
            int current = queue.poll();
            for (int i = 0; i < adj[current].size(); i++) {
                int q = adj[current].get(i);
                if (!visited[q]) {
                    queue.add(q);
                    visited[q] = true;
                    prev[q] = current;
                }
            }
            if (current == des) {
                print(prev, current);
            }
        }
    }

    private void print(int[] prev, int current) {
        if (prev[current] != -1) {
            print(prev, prev[current]);
        }
        System.out.print(current + " -> ");
    }

    public void dfs(int start, int des) {
        found = false;
        boolean visited[] = new boolean[v]; //记录是否被visit了
        visited[start] = true;

        int prev[] = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }
        recurDfs(start, des, visited, prev);
        print(prev, des);
    }

    private void recurDfs(int s, int d, boolean[] visited, int[] prev) {
        if (found) return;
        if (s == d) {
            found = true;
            return;
        }

        for (int i = 0; i < adj[s].size(); i++) {
            int q = adj[s].get(i);
            if (!visited[q]) {
                visited[q] = true;
                prev[q] = s;
                recurDfs(q, d, visited, prev);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(4, 1);
        graph.addEdge(2, 1);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);
        graph.addEdge(2, 5);
        graph.addEdge(5, 7);
        graph.addEdge(4, 6);
        graph.addEdge(6, 7);
//        graph.bfs(0, 7);
        graph.dfs(0, 7);
    }


}
